# Small-world network generator and evaluator
# This code implements the classic Watts-Strogratz algorithm for a small-world network.
# The network can be evaluated as a Cellular Automata (CA) given a specific set of update rules.
#   If p = 0.0 (chance of rewiring connections = zero), then it's like any CA.
#   If p > 0.0, it's small-world network.
#   If p = 1.0, it's a random graph.
# The network can be evaluated as a CA with any p, but the rules will only be deterministic if
# p = 0.0, elsewise the behavior of the system evolution will probably be unpredictable.
 
import random
import datetime

random.seed()

class Node: #Node of the network (or CA cell)
    def __init__(self, i, n_nodes, n_connections, p):
        self.connections = []
        self.value = 0
            
        for j in range(n_connections + 1): 
            target = int((j + i - n_connections/2) % n_nodes) #Regular connection with neighbours 

            if target != i: #Self-connection cannot be rewired, ergo there will always be a "meaningless" self-connection (middle connection)
                if random.random() < p: #Chance this connection will be rewired to a random node
                    target = random.randint(0, n_nodes - 1) #Rewire randomly, obeying some constraints (see function valid_connection)
                    while not self.valid_connection(target, i): 
                        target = random.randint(0, n_nodes - 1)

            self.connections.append(target) #Add connection to node
        
    def valid_connection(self, target, i): #Connection is valid if it's not to itself or to an already connected node
        if target == i: #Cannot create another self-connection
            return False
            
        for j in self.connections: #Cannot create a duplicate connection
            if target == j:
                return False
            
        return True  
        
class SmallWorld: #Small-world network (or CA)
    
    #Initialize network with number of nodes, number of connections per node and probability of rewiring
    def __init__(self, n_nodes, n_connections, p):
        self.n_connections = n_connections
        self.n_nodes = n_nodes
        self.nodes = []
        self.rules = []
        
        #Create "n_nodes" nodes, each with "n_connections" connections to other nodes and a probability "p" of rewiring
        for i in range(n_nodes): 
                self.nodes.append(Node(i, n_nodes, n_connections, p))
    
    #Updates CA evaluation rule using Melanie Mitchell's notation (first bit is the next state of 00...00, second bit of 00...01, third of 00...10)
    def update_rule_mitchell(self, hex_number):
        rules = []
        
        for i in range(2** (self.n_connections + 1)):
            rules.append(0b1 & hex_number)
            hex_number = hex_number >> 1
        
        self.rules = rules[::-1]
    
    #Updates CA evaluation rule using Wolfram's notation (first bit is the next state of 00...00, second bit of 10...00, third of 01...00)
    def update_rule_wolfram(self, hex_number):
        rules = []
        
        for i in range(2** (self.n_connections + 1)):
            rules.append(0b1 & hex_number)
            hex_number = hex_number >> 1
        
        self.rules = rules
    
    def print_CA(self): #Prints the value of each node (0 or 1) of the network on a single space-less line
        for i in self.nodes:
            print(i.value, )
        print("")
    
    def majority(self): #Calculates the majority - m > 0 if there are more 1s than 0s, m < 0 in the opposite case
        m = 0
        for i in self.nodes:
            if i.value == 0:
                m -= 1
            else:
                m += 1
        #print("Majority: " + str(m))
        return m #m also represents the excess of 0s or 1s
        
    def run(self, max_iter): #Run the network as if it were a CA using the last update rule for that for a limited number of iterations
        for iterations in range(max_iter):
            
            for i in self.nodes: #Goes through every node in order
                count = 0
                rule_number = 0
                for j in i.connections[::-1]: #For every node connection
                    #print(j, self.nodes[j].value) 
                    #Searches for update rule considering the value (0 or 1) of each connection, including the self-conneciton
                    rule_number += self.nodes[j].value << count 
                    count += 1
                #Update rule is found depending on the configuration of connections and the value of the node itself
                i.next_value = self.rules[rule_number] 
            
            for i in self.nodes: #Updates the network with the new state
                i.value = i.next_value
                    
            #self.print_CA()
    
    def update_values_randomly(self, rho): #Generates a random initial condition of equal distribution of 0s and 1s
        for i in self.nodes:
            if random.random() < rho:
                i.value = 0
            else:
                i.value = 1
                
    #Evaluate the network (as if were a CA) to solve the majority problem for a N number of times using for each time a different random initial distribution
    def evaluate_majority(self, N): 
        correct = 0
        for i in range(N):
            self.update_values_randomly(0.5)#0.4+random.random()/5.0) #Random initial condition
            initial_majority = self.majority()
            #Run the CA using twice the size of the network as the number of iterations (this is just a heuristic, ideally it would run infinitly) 
            self.run(self.n_nodes*2) 
            final_majority = self.majority() 
            if abs(final_majority) == self.n_nodes: #Found an answer (either all zeros or all ones)
                if initial_majority * final_majority > 0: #Answer is majority of the initial distribution
                    correct += 1
            #correct += float(final_majority)/self.n_nodes * int(initial_majority/abs(initial_majority)) #This gives the percentage of correct cells at the final state
        return float(correct)/N #Return the ratio of correct guesses for the majority problem
"""
a = SmallWorld(99, 6, 0) 
#a.update_rule_mitchell(0x000101170117177701171777177f7fff) #Majority by hand (very bad)
#a.update_rule_mitchell(0x005f005f005f005f005fff5f005fff5f) #GLK (best known rule)
#a.update_rule_mitchell(0x0504058705000f77037755837bffb77f) #Particle (evolved by MM)
#a.update_rule_mitchell(5365274993091967748390686526687265243) #Fitness using fraction of correct cells (evolved by myself)
#a.update_rule_mitchell(340146899268322458001438890170307446884) #Fitness using only correct configurations (evolved by myself)
#a.update_rule_mitchell(340188437653403704167653169250596178020) #?? MM
##a.update_rule_mitchell(340188762156792634892074914178271938660) #?? MM
#a.update_rule_mitchell(266114960702311038779805949386658271) #Fitness using fraction of correct cells (evolved by myself)
a.update_rule_mitchell(11383847509178412160718751131673525916)
#a.update_rule_wolfram(110) #Wolfram rule 110
#a.majority()
#a.print_CA()
#a.run(200)
print(a.evaluate_majority(1000))
"""
